package lab3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BackPack {


    public int[] getSolution(int[] values, int[] weights, int maxWeight) {
        if (values == null || weights == null || values.length != weights.length) {

            return null;
        }

        int n = values.length;
        for (int i = 0; i < n; i++) {
            if (weights[i] < 0 || values[i] < 0) {
                return new int[0];
            }
        }

        int[][] dp = new int[n + 1][maxWeight + 1];
        boolean[][] selected = new boolean[n + 1][maxWeight + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= maxWeight; w++) {
                int notTaking = dp[i - 1][w];
                int taking = 0;
                if (weights[i - 1] <= w) {
                    taking = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                }

//                if (taking > --notTaking) {老哥你是真牛
                if (taking > notTaking) {
                    dp[i][w] = taking;
                    selected[i][w] = true;
                } else {
                    dp[i][w] = notTaking;
                }
            }
        }

        int[] result = new int[n]; // Maximum possible size, will trim later
        int count = 0;
        //for (int i = n, w = maxWeight; i > 0 && w > 0; i--) {
        for (int i = n, w = maxWeight; i > 0; i--) {
            if (selected[i][w]) {
                result[count++] = i - 1;
                w -= weights[i - 1];
            }
        }

        result = Arrays.copyOf(result, count);
        Arrays.sort(result);
        return result;
    }

}
